Functional Programming in F#

Part I — Introduction

Steven Gilham

Based on material developed in collaboration with Will Harwood and Laurence Jordan and presented in 2008

Course Overview

Introduction to Functional Programming via Circuits
- Today's presentation
Lexing and Parsing
Interpreters
Distributed and Concurrent Programming
Advanced topics
- Continuations, monads & computations, etc.
Non-functional bits
- Objects, Exceptions, Libraries, .net, type providers etc.

Introduction to Functional Programming via circuits

Basic Concepts

Introduction to Functional Programming

Background
- and Vocabulary
Digital Circuits
Some Basic Tools

And generalizations

Background

Caveat

This series covers functional-programming concepts, illustrated in F# syntax

It is intended as a way for beginners who have started to use the language to avoid just writing FORTRAN C/C++ old-school C# in an(y )other language.

It is not intended as an introductory guide to the language syntax itself, though I'll put in asides about the notations and concepts used.

What is F#?

F# is a mature, open source, cross-platform, functional-first programming language
- F# Foundation at http://fsharp.org
A .net language

All the familiar tools and libraries

One of the “ML” family of languages

ML 1978
CAML 1985
OCAML 1996
F# 2002

What is an “ML” language?

First class functions
- Familiar from C# LINQ and the delegate, Action and Function types
Strict (“eager”) evaluation
- Arguments evaluated before calling functions
Strongly typed with type inference
Polymorphic (C# “Generic”) and user definable types
Immutable by default
- Mutable references for controlled destructive updates
Garbage Collection
Exception Handling

What is Functional Programming?

No one single agreed definition
“The style of programming where your values are called i, k, and x and your constructs are [something-or-other]-morphisms”
- Plenty of different morphisms to choose from! (examples)
Programming where your functions are pure and your data immutable
Programs as pipelines transforming your data
- As opposed to OO programming where data entities talk to one-another

Digital Circuits

Representation

Our first bit of syntax

Signals have two possible values
- Up/Down, On/Off, True/False, One/Zero ...

type Bit = Zero | One;;

Concept

An Algebraic Data Type

enum on steroids
Can have many values
Can associate data
Are a type (with closed set of sub-types)
Avoid the Primitive Obsession anti-pattern

Concept

Code Fragments

These examples are intended to execute in the F# interactive console.
The ";;" syntax is an ML end-of-expression mark, required to tell the interpreter that there is a compilable unit to process now.
They are not needed in project-based code

Operations

Functions and Pattern matching

Basic operations AND, OR, NOT, XOR

let AND x y = 
  match (x,y) with
  |(Zero, Zero) -> Zero
  |(Zero, One) -> Zero
  |(One, Zero) -> Zero
  |(One, One) -> One ;;

Concept

Functions

AND has two arguments – parentheses are not used to group argument lists
Functions return the value of the last expression evaluated
Everything is an expression.

Concept

Functions ctd.

Neither AND nor its two arguments have explicitly specified types
The compiler inferred them; if it had been unable to, we would have to write
```
let AND (x:Bit) (y:Bit) : (Bit*Bit) = ...
```
The type of AND is Bit -> Bit -> (Bit*Bit)

Concept

A match expression compares one value against an exhaustive list of options and results in the corresponding expression
The one value here is a tuple literal
A simpler way of writing the exhaustive list is to use a wildcard “_” that matches anything
```
let AND x y = 
  match (x, y) with
  | (One, One) -> One
  | _ -> Zero;;
```

Exercise 1.1

There will be more!

Define the standard Bit functions OR, XOR, NOT, NAND, NOR

Digression – Set-up for exercises

Getting and Running F#

Repair install Visual Studio (or grab the latest upgrade if you aren't up to date), and check the F# box under Programming Languages
- Or download Visual F# Tools 4.0 RTM (https://www.microsoft.com/en-us/download/details.aspx?id=48179)
All these exercises will be done in F# interactive mode, either
- Open the F# Interactive Window in Visual Studio
- Run 'C:\Program Files (x86)\Microsoft SDKs\F#\4.0\Framework\v4.0\Fsi.exe' at a cmd or PowerShell prompt

Digital Circuits
Continues...

Binary Addition

An adder takes two streams of bits and produces a steam of bits as the answer

Initial Condition: carry output is Zero

Half-Adder and Full-Adder

In standard fashion, we build an adder from two half-adders (which take two inputs and produce the XOR as the sum stream and the AND as the carry stream)

let Half_Adder x y =
 (XOR x y, AND x y);;

One half-adder takes the two inputs; the sum stream from that is passed into the second half-adder along with the previous carry bit, and the resulting sum forms the final output.

The two intermediate carry streams are OR'd together to form the full carry stream

let Full_Adder x y z = 
  let (s1, c1) = Half_Adder x y
  let (s2, c2) = Half_Adder s1 z
  (s2, OR c1 c2);;

Concept

The “=“ is mathematical – the left hand side is that thing which satisfies the equation
Binds a value to a name
The LHS is a limited pattern match; a tuple RHS can be equated to a tuple LHS – a “destructuring” binding.
Use “_” for a “don’t care value here too!

Exercise 1.2

Write Full_Adder as a pattern match operation, without any auxiliary half-adder function

Some Basic Tools

Lists and Streams

Basic functional concepts

A well typed list is a sequence of values where all the values are of the same type,say, 'a. This is an 'a list e.g. Bit list
A list is either empty or it is a pair of values composed of a value of type 'a and an 'a list

(* introduce the built in type of lists: 
	this is both recursive and polymorphic *)

// type 'a list =   []
//                | (::) of 'a * 'a list

Concept

“//” introduces a comment for the rest of the line
“(*” and “*)” indicate a block comment
This “definition” of list is descriptive only
“::” is the function (operator) that prepends an item to a list
Infix operators are just functions with special syntax

Structural Recursion

Define a function by what it must do on each clause of the type definition

The length of an empty list is 0
The length of a non-empty list is 1 + the length of the rest of the list

let rec length l =
   match l with
   | [] -> 0
   | (x::xs) -> 1 + (length xs);;

Concept

“rec” defines a recursive function
It simply means that the function's name is visible inside its own body
To avoid the need for mutable counters or flags, recursion replaces loops for iterative operations.

More Structural Recursion

let rec append l1 l2 =
  match l1 with
  | [] -> l2
  | (x::xs) -> x::(append xs l2);;

(* simple and inefficient reverse 
by structural recursion*)‏
let rec rev l =
  match l with
  | [] -> []
  | (x::xs) -> append (rev xs) [x];;

Higher-order functions

Functions as values

```
let twice f x = f (f x);;
```
- f is a function
- Parentheses group the sub-expression, making the order of evaluation explicit
```
(fun x -> x * x)
```
- Lambda expression (free-standing anonymous function) to compute a square
- Implicitly of type int -> int
```
(fun x -> x * x) 4;;
```
- → 16
```
twice (fun x -> x * x) 4;;
```
- → 256

Concept

F# defines these very useful higher-order functions as infix operators
```
let (|>) f x = f x
let (>>) f g x = f(g x)
```

So we can write

let twice f x = f |> f x;;

let twice f = f >> f;;

|> is F#'s answer to fluent syntax

Generalising

We can build upon the pieces

let rec power f n x =
  if n <= 0
    then x
    else power f (n – 1) (f x);;

Map/Reduce

Apply a function to each element of a list, giving a new list

let rec map f l =
  match l with
  |[] -> []
  |(x::xs) -> (f x)::(map f xs);;

Accumulate over a list

let rec reduce f c l =
  match l with
  |[] -> c
  |(x::xs) -> f x (reduce f c xs);;

= f(x₁, f(x₂, … f(x_n,c) … ))

Another definition of length

let len l = reduce ( + ) 0 (map (fun x -> 1) l);;

Concept

In the expression
```
let len l = reduce ( + ) 0 (map (fun x -> 1) l);;
```
the infix operator “plus” is named in parentheses
This is the same as in the declaration of an infix operator function
! % & * + - . / < = > ? @ ^ | and ~ are allowed in user-defined (infix operator) function names

Exercise 1.3

Define the function zip which when given two lists of the same length and returns a single list of pairs
zip [1;2;3] [Zero; One; Zero] → [(1,Zero); (2,One); (3,Zero)]
Define itlist which takes a function f, an initial value v, and a non-negative integer n and returns a list of the iterates of f on v
itlist f v n → [v; f v; f(f v); f(f(f v))); ....; fⁿ v]
Define R_reduce f l c → f(x_n...f(x₂, f(x₁, c)))

The Adder

let rec R_Adder bl1 bl2 c =
  match (bl1, bl2) with
  | ([],[]) -> []
  | (x::xs, y::ys) -> 
      let (out, carry) = (Full_Adder x y c)
      out::(R_Adder xs ys carry)
  | _ -> [];;

Note the lists are assumed to be in Least Significant Bit first order

Tidying Up

The numbers may not be the same length
- Drop leading zeroes
- Pad to matching length
We read numbers Most Significant Bit first
- Reverse lists before and after addition
- We already defined reverse above

let rec dropleadingzeros l =
  match l with
  | [] -> []
  | (Zero::xs) -> dropleadingzeros xs
  | x -> x;;

// add n leading Zero's 
let rec padby n l = if n <= 0 
  then l 
  else padby (n-1) (Zero::l);;

// pad two lists to the same length
let rec pad (l1, l2) = 
  let len1 = length l1
  let len2 = length l2
  if (len1 = len2) then (l1,l2)
  else if (len1 < len2) then (padby (len2-len1) l1, l2)
       else (l1, padby  (len1-len2) l2);;

Putting It All Together

let Adder bl1 bl2 =
  let (l1,l2) = pad ((dropleadingzeros bl1), (dropleadingzeros bl2))
  reverse(R_Adder (reverse (Zero::l1)) (reverse (Zero::l2)) Zero);;

Generalising : the Synchronous State Machine

let rec Mach f s l =
  match l with
  | [] -> []
  | (x::xs) -> 
    let (out, state) = (f x s)
    out::(Mach f state xs);;
let X_R_Adder bl1 bl2 c = 
   let UC_Full_Adder (a,b) c = Full_Adder a b c
   Mach UC_Full_Adder Zero (zip bl1 bl2);;
let PAdder bl1 bl2 =
  let (l1,l2) = pad ((dropleadingzeros bl1), (dropleadingzeros bl2))
  rev(X_R_Adder (rev (Zero::l1)) (rev (Zero::l2)));;

Functional Programming in F#

Part I — Introduction

Course Overview

Introduction to Functional Programming via circuits

Introduction to Functional Programming

Background

Caveat

What is F#?

What is an “ML” language?

What is Functional Programming?

Digital Circuits

Representation

Concept

Concept

Operations

Concept

Concept

Concept

Exercise 1.1

Digression – Set-up for exercises

Getting and Running F#

Digital CircuitsContinues...

Binary Addition

Half-Adder and Full-Adder

Concept

Exercise 1.2

Some Basic Tools

Lists and Streams

Concept

Structural Recursion

Concept

More Structural Recursion

Higher-order functions

Concept

Generalising

Map/Reduce

Concept

Exercise 1.3

The Adder

The Adder

Tidying Up

Putting It All Together

Generalising : the Synchronous State Machine

Wrapping up

つづく

Digital Circuits
Continues...